Applicants' invention relates to apparatus and methods for using radio channel characteristics to generate pseudorandom quantities at plural transceivers that can be used, for example, as spreading sequences in communicating using code division multiplexing or code division multiple access (CDMA) systems or as frequency hopping sequences in time division multiple access (TDMA) or CDMA systems.
The widespread need for secure communication in radio communication systems is apparent. As just two examples, information relating to financial transactions is routinely exchanged by radio, and law enforcement officers often must communicate voice and/or data by radio. In both examples, it is critical that the communication be conducted with almost perfect secrecy, despite potential eavesdroppers' having access to strong information signals. Users of cellular radiotelephones also desire privacy in their communications, which may travel on links between mobile phones and base stations or on direct links between mobiles.
One way of providing security is to encrypt the communicated information according to some system that the users have agreed in advance to use. Several encryption methods have been described in the literature, such as the data encryption standard (DES) and public key cryptography (PKC). As explained in W. Diffie et al., "Privacy and Authentication: An Introduction to Cryptography", Proc. IEEE vol. 67, pp. 397-427 (March 1979), a classical cryptographic system is in general a set of instructions, a piece of hardware, or a computer program that can convert plain text (unencrypted information) to ciphertext, or vice versa, in a variety of ways, one of which is selected by a specific key that is known to the users but is kept secret from others. The DES is a classical cryptographic system.
Popular PKC systems make use of the fact that finding large prime numbers is computationally easy but factoring the products of two large prime numbers is computationally difficult. PKC systems have an advantage over other cryptographic systems like the DES in that a PKC system uses a key for decryption that is different from the key for encryption. Thus, a PKC user's encryption key can be published for use by others, and the difficulty of securely distributing keys is avoided. See, e.g., R. I. Rivest et al., "A Method of Obtaining Digital Signatures and Public-Key Cryptosystems", Commun. of the ACM vol. 21, pp. 120-126 (February 1978); and W. Diffie, "The First Ten Years of Public-Key Cryptography", Proc. IEEE vol. 76, pp. 560-577 (May 1988).
For either a classical or PKC system, the security of a message is dependent to a great extent on the length of the key, as described in C. E. Shannon, "Communication Theory of Secrecy Systems", Bell Sys. Tech. J. vol. 28, pp. 656-715 (October 1949).
Unfortunately, it is often the case that two users (two police officers, for instance) do not share a secret key a priori, making secure real-time communication via a classical crytographic system impossible. Even a PKC system requires a user to generate a pseudo-random quantity. Moreover, popular PKC systems are unprovably secure, and suffer from severe requirements in computational complexity and amount of information that must be exchanged. As new ways of attacking PKC systems are mounted, PKC systems will retreat to ever longer exchange vectors (in effect, larger prime numbers) and ever more complex computations. As a result, classical and PKC cryptographic systems are less than ideal for many communication situations.
Complicating the task of any radio communication system is the variability of the radio channel caused by atmospheric disturbances, relative motion of the system users, changing radio signal reflections from structures and vehicles, etc. Such channel variability contributes to errors in the information communicated, and much effort is expended to overcome these errors. For example, some cellular radiotelephone systems convert analog information to be transmitted into digital information, which is then transformed according to a block error correction code. Such a cellular radio system is specified in TIA/EIA/IS-95-A, which is an interim standard published by the Telecommunications Industry Association and Electronic Industries Association (TIA/EIA) for a North American CDMA communication system and the disclosure of which is incorporated here by reference.
In such a CDMA system, each radio channel, or radio carrier signal having a particular frequency, corresponds to a respective spreading sequence of digital bits that is used for encoding a sequence of information bits from a data source, e.g., a digitally encoded portion of a voice conversation. The information sequence to be communicated is spread, or mapped, into a longer sequence by combining the information sequence with the spreading sequence. As a result, one or more bits of the information sequence are represented by a sequence of N "chip" values. The sequence of chips, i.e., the spread information sequence, is then used to modulate the frequency of the radio carrier signal.
For example, at a transmitter, a binary information symbol b (.+-.1) can be spread by multiplying b with a spreading sequence x; for example, the spreading sequence x might be +1, -1, +1, -1, consisting of four binary chips. In essence, the spreading process replaces each binary information symbol with a four-chip spread symbol: +1, -1, +1, -1 when b=+1; and -1, +1, -1, +1 when b=-1. In this process called "direct spreading", each spread symbol is essentially the product of an information symbol and the spreading sequence.
In a second form of spreading called "indirect spreading", the different possible information symbols are replaced by different, not necessarily related, spreading sequences. Such mapping from information symbol to spread symbol can be viewed as a form of block coding. In the general case, a single M-ary information symbol, i.e., a symbol that can take on any of M possible values, is mapped to one of M possible spread symbols. In the binary case, the symbol b=+1 might be replaced by the sequence x=+1, -1, +1, -1, and the symbol b=-1 might be replaced by the sequence y=+1, +1, -1, -1.
In either direct or indirect spreading, the information symbol may be derived from a differential symbol d. For example, a binary information symbol b at a time n (denoted b(n)) may be determined by the information symbol at a time n-1 (denoted b(n-1)) and a differential information symbol d at the time n (denoted d(n)) according to the following relationship: EQU b(n)=b(n-1)d(n)
which gives: EQU d(n)=b(n)b*(n-1)
where * denotes complex conjugate. Also, it will be understood that the information symbols described above may be produced by preceding stages of channel coding and/or spreading.
An advantage of such spreading is that information from many sources can be transmitted at the same time in the same radio frequency band, provided the spreading sequences used to represent the different sources' information sequences do not interfere with one another too much. In effect, the different spreading sequences correspond to different communication "channels".
Various aspects of conventional CDMA communications are described in K. Gilhousen et al., "On the Capacity of a Cellular System," IEEE Trans. Veh. Technol. vol. 40, pp. 303-312 (May 1991). Other aspects of CDMA communication systems are described in U.S. patent application No. 08/291,693 filed Aug. 16, 1994, by Bottomley et al. for "Multiple Access Coding using Bent Sequences for Mobile Radio Communications", and in the following U.S. patent documents: U.S. Pat. No. 5,151,919 to Dent; and U.S. Pat. No. 5,353,352 to Dent et al.; and allowed U.S. patent application No. 08/155,557 filed Nov. 22, 1993. These patents and patent applications are expressly incorporated here by reference.
To minimize interference among the channels due to their overlap in time and frequency, the spreading sequences should be as random as possible (and thus the CDMA channels) can also be mutually orthogonal, i.e., the cross-correlations of the spreading sequences must be zero. (Two binary sequences are orthogonal if they differ in exactly one-half of their bit positions.) On the other hand, there are only N orthogonal spreading sequences of length N.
It may be recognized that spreading an information sequence by combining it with one of a set of orthogonal spreading sequences is similar to the common process of block coding. In many communication systems, an information sequence to be communicated is block-coded for correcting errors. In orthogonal block coding, a number N of information bits are converted to one of 2.sup.N N-bit orthogonal codewords. Decoding such an orthogonal codeword involves correlating it with all members of the set of 2.sup.N codewords. The binary index of the codeword giving the highest correlation yields the desired information. For example, if the correlations of a received 16-bit codeword with each of the set of sixteen orthogonal 16-bit codewords having indices 0-15 produce the highest correlation on the tenth codeword, the underlying information signal is the 4-bit binary codeword 1010 (which is the integer ten in decimal notation). Such a code is called a [16,4] orthogonal block code. By inverting all of the bits of the codewords, one further bit of information may be conveyed per codeword. This type of coding is known as bi-orthogonal block coding.
A significant feature of such coding is that simultaneous correlation with all the orthogonal block codewords in a set may be performed efficiently by means of a Fast Walsh Transform (FWT) device. In the case of a [128,7] block code, for example, 128 input signal samples are transformed into a 128-point Walsh spectrum in which each point in the spectrum represents the value of the correlation of the input signal samples with one of the codewords in the set. A suitable FWT processor is described in U.S. Pat. No. 5,357,454 to Dent, which is incorporated here by reference.
As noted above, the typical CDMA system spreads an information sequence into block error correction codewords, and then combines the block codewords with a code sequence that is unique to each user. In the system described in U.S. Pat. No. 5,353,352, the block codewords are combined with a scramble mask that does not further spread the information sequence.
Another technique for combatting interference in CDMA systems (or TDMA systems) is known as frequency hopping. Frequency hopping is a technique for ensuring that worst case interference scenarios do not prevail for longer than one frequency hop interval, rather than for the duration of an entire connection by changing the carrier frequency used on which data symbols associated with the connection are modulated. This characteristic is commonly known as interferer diversity. Frequency hopping also provides frequency diversity that combats fading for slowly moving mobile stations. Moreover, frequency hopping can also be used to eliminate the difficult task of frequency planning, which is of special importance in microcells. This can be achieved if all of the cells in a system use the same frequencies but each cell has a different hop sequence. Such systems have been called Frequency Hopping Multiple Access (FHMA) systems.
In a frequency hopping system each cell can use all of the available frequencies, but at different times, as determined by a pseudo-random frequency hop sequence generator. Such generators can be constructed several ways, e.g., to yield a random probability that any two cells choose the same frequency at the same time (known as non-orthogonal hopping), to guarantee that specified cells or mobile stations never choose the same frequency at the same time (known as orthogonal hopping), or to obtain a mixture of the preceding two techniques (e.g., signals in the same cell hop orthogonally, while being non-orthogonal relative to signals in adjacent cells).
Spreading sequences in CDMA systems and frequency hopping sequences in TDMA or CDMA systems have in common a desired pseudorandom characteristic which is designed to aid in reducing overall system interference. Conventional systems generate these types of sequences using pseudorandom number generators. These pseudorandom number generators have several drawbacks. For example, they typically are limited in the number of pseudorandom sequences that they can generate. Moreover, these devices require extensive memories for facilitating sequence generation. Yet another drawback to the use of pseudorandom number generators as components of base stations and mobile stations in radiocommunication systems is that they must use an elaborate scheme of common inputs to ensure that a base station and a mobile station that are communicating with one another generate the same pseudorandom sequence so that they can, for example, properly spread and despread CDMA composite signals.